public class test {
    //leetcode 978.最长湍流子数组
    class Solution {
        // 解法1. 滑动窗口
        public int maxTurbulenceSize1(int[] arr) {
            int n = arr.length;
            int left = 0;
            int max = 1;
            for (int right = 0; right < n - 1;) {
                if (left == right) {
                    if (arr[left] == arr[left + 1]) {
                        left++;
                    }
                    right++;
                } else {
                    // 如果不是湍流数组,则重新计数
                    if (!(arr[right - 1] > arr[right] && arr[right] < arr[right + 1])
                            && !(arr[right - 1] < arr[right] && arr[right] > arr[right + 1])) {
                        left = right;
                    } else {
                        right++;
                    }
                }
                max = Math.max(max, right - left + 1);
            }
            return max;
        }

        // 解法2. 动态规划
        public int maxTurbulenceSize(int[] arr) {
            // 1. 创建dp表
            int n = arr.length;
            //代表以i下标结束时为升序的最长湍流子数组长度
            int[] f = new int[n];
            //代表以i下标结束时为降序的最长湍流子数组长度
            int[] g = new int[n];
            // 2. 初始化
            int max = 1;
            Arrays.fill(f,1);
            Arrays.fill(g,1);
            // 3. 填表
            for(int i = 1;i < n;i++){
                //代表此时升序,寻找降序
                if(arr[i] > arr[i - 1]){
                    g[i] = Math.max(f[i - 1] + 1,g[i]);
                }else if(arr[i] < arr[i - 1]){
                    f[i] = Math.max(g[i - 1] + 1,f[i]);
                }
                max = Math.max(max,f[i]);
                max = Math.max(max,g[i]);
            }
            // 4. 返回值
            return max;
        }
    }
    //leetcode 139.单词拆分
    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> set = new HashSet(wordDict);
            int n = s.length();
            boolean[] dp = new boolean[n + 1];
            dp[0] = true;
            s = " " + s;
            for(int i = 1;i <= n;i++){
                for(int j = i;j > 0;j--){
                    if(dp[j - 1] && set.contains(s.substring(j,i + 1))){
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[n];
        }
    }
    //leetcode 300.最长递增子序列
    class Solution {
        public int lengthOfLIS(int[] nums) {
            // 1. 创建dp[]表
            int n = nums.length;
            int[] dp = new int[n];
            // 2. 初始化
            int max = 1;
            //将所有情况先初始化为1,省去中间步骤
            Arrays.fill(dp, 1);
            // 3. 填表
            for (int i = 1; i < n; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                max = Math.max(dp[i], max);
            }
            // 4. 返回值
            return max;
        }
    }
    //leetcode 376.摆动序列
    class Solution {
        public int wiggleMaxLength(int[] nums) {
            // 1. 创建dp表
            int n = nums.length;
            // f[]代表以递增为结束的i位置之前最长的摆动序列
            int[] f = new int[n];
            // g[]代表以递减为结束的i位置之前最长的摆动序列
            int[] g = new int[n];
            // 2. 初始化
            Arrays.fill(f, 1);
            Arrays.fill(g, 1);
            int max = 1;
            // 3. 填表
            for (int i = 1; i < n; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (nums[i] > nums[j]) {
                        f[i] = Math.max(g[j] + 1, f[i]);
                    }
                    if (nums[i] < nums[j]) {
                        g[i] = Math.max(f[j] + 1, g[i]);
                    }
                }
                max = Math.max(max, f[i]);
                max = Math.max(max, g[i]);
            }
            // 4. 返回值
            return max;
        }
    }
}
